package LeetCode刷题.暑假刷的算法;

import java.util.HashMap;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-07-19 09:01
 * @description: Functions of this class is 通过一组数据，找到该路线的终点，与起点
 **/
public class 终点与起点 {
    public static void main(String args[]) {
        HashMap<String, String> map = new HashMap<>();
        map.put("北京", "上海");
        map.put("大连", "西安");
        map.put("上海", "大连");
        map.put("西安", "成都");

        findPath(map);
    }

    private static void findPath(HashMap<String, String> map) {
        //先构造一个逆序的HashMap
        HashMap<String, String> reverse = new HashMap<>();
        for (HashMap.Entry<String, String> m : map.entrySet()) {
            reverse.put(m.getValue(), m.getKey());
        }
        //然后开始将正序表与逆序表进行比对，从中找看有没有k-v不相同的，
        String start = null;
        for (HashMap.Entry<String, String> m : map.entrySet()) {
            if (!reverse.containsKey(m.getKey())) {//因为不可能有闭环，所以起点作为的Key，在逆序的表中是一定没有Value的
                start = m.getKey();
                break;
            }
        }
        if (start == null) {
            System.out.println("输入有误，该数据没有起始点，为闭环！");
            return;
        }
        System.out.println("起点为：" + start);
        String end = null;//若有起点，则直接通过起点找到终点即可
        String x = map.get(start);//先找到下一个地点
        System.out.print("路线为：" + start + "->");
        while (x != null) {
            start = x;
            x = map.get(start);
            if (x == null) {
                break;
            }
            System.out.print(start + "->");
            end = x;
        }
        System.out.println(end);
    }
}